package com.chj.zhongji.class07;

import java.util.Arrays;
import java.util.Comparator;

//https://leetcode-cn.com/problems/russian-doll-envelopes/
public class Code02_EnvelopesProblem {

	public static class Envelope {
		public int l;
		public int h;

		public Envelope(int weight, int hight) {
			l = weight;
			h = hight;
		}
	}

	public static class EnvelopeComparator implements Comparator<Envelope> {
		@Override
		public int compare(Envelope o1, Envelope o2) {
//			return o1.l != o2.l ? o1.l - o2.l : o2.h - o1.h;
			if (o1.l != o2.l) {
				if (o1.l > o2.l) {
					return 1;
				} else if (o1.l < o2.l) {
					return -1;
				} else {
					return 0;
				}

			} else {

				if (o1.h > o2.h) {
					return -1;
				} else if (o1.h < o2.h) {
					return 1;
				} else {
					return 0;
				}
			}
		}
	}

	public static Envelope[] getSortedEnvelopes(int[][] matrix) {
		Envelope[] res = new Envelope[matrix.length];
		for (int i = 0; i < matrix.length; i++) {
			res[i] = new Envelope(matrix[i][0], matrix[i][1]);
		}
		Arrays.sort(res, new EnvelopeComparator());
		return res;
	}

	public static int maxEnvelopes(int[][] matrix) {
		Envelope[] envelopes = getSortedEnvelopes(matrix);
		int[] ends = new int[matrix.length];
		int[] dp = new int[matrix.length];
		ends[0] = envelopes[0].h;
		int right = 0;
		int l = 0;
		int r = 0;
//		int m = 0;

		int res = Integer.MIN_VALUE;
		for (int i = 1; i < envelopes.length; i++) {
			l = 0;
			r = right;
//			while (l <= r) {
//				m = (l + r) / 2;
//				if (envelopes[i].h > ends[m]) {
//					l = m + 1;
//				} else {
//					r = m - 1;
//				}
//			}
			l = left_bound(ends, envelopes[i].h, l, r);
			right = Math.max(right, l);
			ends[l] = envelopes[i].h;
			dp[i] = l + 1;
			res = Math.max(res, dp[i]);
		}
		return res;
//		return right + 1;
	}

	public static int left_bound(int[] nums, int target, int l, int r) {
		int left = l, right = r;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] < target) {
				left = mid + 1;
			} else if (nums[mid] > target) {
				right = mid - 1;
			} else if (nums[mid] == target) {
				// 别返回，锁定左侧边界
				right = mid - 1;
			}
		}
		// 最后要检查 left 越界的情况
//		if (left >= nums.length || nums[left] != target)
//			return -1;
		return left;
	}

	public static void main(String[] args) {
		int[][] test = { { 3, 4 }, { 2, 3 }, { 4, 5 }, { 1, 3 }, { 2, 2 }, { 3, 6 }, { 1, 2 }, { 3, 2 }, { 2, 4 } };
		System.out.println(maxEnvelopes(test));
		int[][] envelopes = { { 5, 4 }, { 6, 4 }, { 6, 7 }, { 2, 3 } };
		System.out.println(maxEnvelopes(envelopes));
	}
}
